package leetcode.tree;

import java.util.HashMap;
import java.util.LinkedList;

public class Lc437 {
    int ans = 0; //连续多个节点的sum==targetSum的个数
    HashMap<Long, Integer> preSum = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        preSum.put(0L, 1);
        searchTree(root, targetSum, 0L);
        return ans;
    }
    private void searchTree(TreeNode root, int targetSum, long sum) {
        if (root == null) return;
        sum += root.val;
        ans += preSum.getOrDefault(sum - targetSum, 0);
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        searchTree(root.left, targetSum, sum);
        searchTree(root.right, targetSum, sum);
        preSum.put(sum, preSum.get(sum) - 1);
    }


    public static void main(String[] args) {
        Lc437 lc437 = new Lc437();
        TreeNode t5 = new TreeNode(-1,null,null);
        TreeNode t4 = new TreeNode(1,t5,null);
        TreeNode t3 = new TreeNode(3,null,null);
        TreeNode t2 = new TreeNode(-2,t4,t3);
        TreeNode t1 = new TreeNode(1,t2,null);
        System.out.println(lc437.pathSum(t1, 0));


    }

}
